package com.example.leetdemo.optimize;

public class Solution743 {

    int MAX_VALUE = 10000007;

    public int networkDelayTime(int[][] times, int n, int k) {
        int[][] w = new int[n + 1][n + 1];
        for (int i = 0; i < n + 1; i++) {
            for (int j = 0; j < n + 1; j++) {
                w[i][j] = i == j ? 0 : MAX_VALUE;
            }
        }
        for (int i = 0; i < times.length; i++) {
            w[times[i][0]][times[i][1]] = times[i][2];
        }
        for (int p = 1; p <= n; p++) {
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    w[i][j] = Math.min(w[i][j], w[i][p] + w[p][j]);
                }
            }
        }
        int max = 0;
        for (int i = 1; i <= n; i++) {
            if (w[k][i] == MAX_VALUE && k != i) {
                return -1;
            }
            if (k != i) {
                max = Math.max(w[k][i], max);
            }
        }
        return max;
    }

    public static void main(String[] args) {
        Solution743 solution743 = new Solution743();
        int k = solution743.networkDelayTime(new int[][] {
                {1,2,1}, {1,3,4}, {2,3,2}
        }, 3, 1);
        System.err.println(k);
        // todo doMore
    }
}
